package data.structure;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Darkness Shadow
 * @description: 循环队列
 * @date 2019/12/27 23:18
 */
@Data
public class MyCircularQueue {

    private List<Integer> data;
    private Integer endIndex;
    private Integer startIndex;
    private Integer len;

    public  MyCircularQueue(int k) {
        len = k;
        data = new ArrayList<>(k);
        for(int i = 0;i < len;i++){
            data.add(null);
        }
        startIndex = 0;
        endIndex = 0;
    }

    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        if (startIndex == 0 && data.get(0) == null) {
            return true;
        }
        return false;
    }

    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        if ((startIndex < endIndex && endIndex - startIndex == len - 1) ||
                (startIndex > endIndex && endIndex + 1 == startIndex)){
            return true;
        }
        return false;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty() || endIndex == len - 1) {
            endIndex = 0;
            data.set(endIndex, value);
        }else {
            endIndex ++;
            data.set(endIndex, value);
        }
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (startIndex == endIndex) {
            data.set(startIndex,null);
            startIndex = endIndex = 0;
        }else if(startIndex < endIndex || (startIndex > endIndex && startIndex < len - 1)){
            data.set(startIndex, null);
            startIndex ++;
        } else {
            data.set(startIndex, null);
            startIndex = 0;
        }
        return true;
    }

    /** Get the front item from the queue. */
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return data.get(startIndex);
    }

    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data.get(endIndex);
    }


    /** 队列长度为4
     *  队列为空 ： s = end data=null
     *  队列为1：S = 0,end = 0,data !=null
     *  队列为2：S = 0,end = 1,data !=null
     *  队列为3：S = 0,end = 2,data !=null
     *  队列为4：S = 0,end = 3,data !=null
     *  队列为3：s = 1,end = 3,data != null
     *  队列为4：s = 1,end = 0,data != null
     */






    public static void main(String [] args) {
        MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3

        System.out.println(circularQueue.enQueue(1));  // 返回 true

        System.out.println(circularQueue.enQueue(2));  // 返回 true

        System.out.println(circularQueue.enQueue(3));  // 返回 true

        System.out.println(circularQueue.enQueue(4));  // 返回 false，队列已满

        System.out.println(circularQueue.Rear());  // 返回 3

        System.out.println(circularQueue.isFull());  // 返回 true

        System.out.println(circularQueue.deQueue());  // 返回 true

        System.out.println(circularQueue.enQueue(4));  // 返回 true

        System.out.println(circularQueue.Rear());  // 返回 4
    }
}
